//============================================================================
// Name        : 7_3_Linux.cpp
// Author      : Eric Chen
// Version     :
// Copyright   : Your copyright notice
// Description : Stooge sort in C++, Ansi-style
//============================================================================


#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>


using namespace std;

int SimapleArray[]={13,19,9,5,12,8,7,4,11,2,6,21};
class PrintInt
{
	public:
		void operator()(int elem) const
		{
			cout << elem<<' ';
		}
};
//i,i from zero this time, I can stand from one anymore!

void stooge_sort(vector<int> &vec,int i, int j)
{
	if(vec[i]>vec[j])
		swap(vec[i],vec[j]);
	if(i+1>=j)
		return;
	int k=floor((j-i+1)/3);
	stooge_sort(vec,i,j-k);
	stooge_sort(vec,i+k,j);
	stooge_sort(vec,i,j-k);

}

int main()
{
	vector<int> A;
	int size=sizeof(SimapleArray)/sizeof(int);
	for(int i=0;i<size;i++)
	{
		A.push_back(SimapleArray[i]);
	}
	cout << "Array before sorting\n";
	for_each(A.begin(), A.end(), PrintInt());
	cout<<endl;
	cout << "Stooge sorts the array"<<endl;
	stooge_sort(A,0,size-1);
	cout << "Array after sorting\n";
	for_each(A.begin(), A.end(), PrintInt());
	cout<<endl;
	return 0;
}
